package leetcode.editor.cn;


//在给定的 m x n 网格
// grid 中，每个单元格可以有以下三个值之一：
//
//
// 值 0 代表空单元格；
// 值 1 代表新鲜橘子；
// 值 2 代表腐烂的橘子。
//
//
// 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
//
// 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
//
//
//
// 示例 1：
//
//
//
//
//输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
//输出：4
//
//
// 示例 2：
//
//
//输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
//输出：-1
//解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
//
//
// 示例 3：
//
//
//输入：grid = [[0,2]]
//输出：0
//解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
//
//
//
//
// 提示：
//
//
// m == grid.length
// n == grid[i].length
// 1 <= m, n <= 10
// grid[i][j] 仅为 0、1 或 2
//
//
// Related Topics 广度优先搜索 数组 矩阵 👍 978 👎 0


import java.util.Queue;
import java.util.LinkedList;


//Java：腐烂的橘子
public class RottingOranges{
    public static void main(String[] args) {
        Solution solution = new RottingOranges().new Solution();
        // TO TEST
        solution.orangesRotting(new int[][]{{0}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int orangesRotting(int[][] grid) {

        /**
         * 思路：橘子腐烂是一层一层的，很符合BFS
         * 先统计最开始腐烂橘子的数量，并且加入队列，作为遍历的起始节点
         *  然后在遍历队列，把当前时间内，腐烂的橘子的感染上下左右的橘子，并且把最新的腐烂的橘子加入到队列里面去
         *   循环的借宿条件就是当前队列里没有最外层的腐烂橘子了，也就是不会再感染新的橘子了
         *   最后判断返回结果
         */
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int fresh = 0;
        int time = 0;
        //计算出 新鲜和腐烂橘子的数量
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if(grid[i][j] == 2){
                    //腐烂的橘子
                    queue.offer(new int[]{i,j});
                }
                if(grid[i][j] == 1){
                    //新鲜的橘子
                    fresh++;
                }
            }
        }
        ///如果没有腐烂的橘子作为起始点，那就返回-1
        if(queue.isEmpty() && fresh!=0) return -1;
        if(fresh == 0) return 0;

        //while循环，当queue为空，并且fresh为0，则返回time
        while (!queue.isEmpty() && fresh > 0){
            int size = queue.size();
            //遍历队列，统计腐烂橘子在当前时间的腐烂，并且把最新的腐烂橘子加入到队列里面去
            for (int i = 0; i < size; i++){
                int[] peek = queue.poll();
                int x=peek[0];
                int y=peek[1];
                //腐烂上下左右
                //上
                if(x - 1 >= 0 && grid[x - 1][peek[1]] == 1){
                    grid[x - 1][peek[1]] = 2;
                    queue.offer(new int[]{x - 1,peek[1]});
                    fresh--;
                }
                //下
                if(x + 1 < m && grid[x + 1][peek[1]] == 1){
                    grid[x + 1][peek[1]] = 2;
                    queue.offer(new int[]{x + 1,peek[1]});
                    fresh--;
                }
                //左
                if(y - 1 >= 0 && grid[peek[0]][y - 1] == 1){
                    grid[peek[0]][y - 1] = 2;
                    queue.offer(new int[]{peek[0],y - 1});
                    fresh--;
                }
                //右
                if(y + 1 < n && grid[peek[0]][y + 1] == 1){
                    grid[peek[0]][y + 1] = 2;
                    queue.offer(new int[]{peek[0],y + 1});
                    fresh--;
                }
            }
            time++;
        }

        return fresh == 0 ? time : -1;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
